package test.n00400;


import static utils.Tools.listOf;

public class Problem00410 {
    public static void main(String[] args) {
        //println(new int[]{1, 1, 3, -2});
        //println(new int[]{0, 2, 1});
        println(new int[]{3, 4, -1, 1});
    }

    public static void println(int[] nums) {
        Solution ss = new Solution();
        System.out.println(listOf(nums) + "," + ss.firstMissingPositive(nums));
    }

    public static class Solution {

        /**
         * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
         * <p>
         * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
         * <p>
         * 解题思路:
         * hash法
         *
         * @param nums
         * @return
         */
        public int firstMissingPositive(int[] nums) {
            int n = nums.length;
            for (int i = 0; i < n; i++) {
                if (nums[i] <= 0) {
                    nums[i] = n + 1;
                }
            }

            for (int i = 0; i < n; i++) {
                int t = Math.abs(nums[i]);
                if (t <= n) {
                    nums[t - 1] = -Math.abs(nums[t - 1]);
                }
            }

            for (int i = 0; i < n; i++) {
                if (nums[i] > 0) {
                    return i + 1;
                }
            }

            return n + 1;
        }
    }
}
